/**
 * 
 */
package dp.passed2;

/**
 * @author xyyi
 *
 */
public class ScrambleString {

	/**
	Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

	Below is one possible representation of s1 = "great":

	great
	/    \
	gr    eat
	/ \    /  \
	g   r  e   at
	       / \
	      a   t
	To scramble the string, we may choose any non-leaf node and swap its two children.

	For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

	rgeat
	/    \
	rg    eat
	/ \    /  \
	r   g  e   at
	       / \
	      a   t
	We say that "rgeat" is a scrambled string of "great".

	Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

	rgtae
	/    \
	rg    tae
	/ \    /  \
	r   g  ta  e
	   / \
	  t   a
	We say that "rgtae" is a scrambled string of "great".

	Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
	 */

	/*
	#1 Solution, DP
	dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble
	string。
	
	string x y
	x = x1x2, y = y1y2
	1. 如果两个substring相等的话，则为true
	x == y

	2. 如果两个substring中间某一个点，左边的substrings为scramble string，
	同时右边的substrings也为scramble string，则为true
	string x y
	x = x1x2, y = y1y2
	isScramble(x1, y1) and isScrable(x2, y2)

	3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为scramble
	string, 同时s1右边substring和s2左边的substring也为scramble
	string，则为true
	isScramble(x1, y2) and isScramble(x2, y1)

	 */
	public boolean isScramble(String s1, String s2) {
		if (s1.length() != s2.length())
			return false;

		int length = s1.length();
		boolean[][][] dp = new boolean[length][length][length + 1];// i,j,k s1 starts with i, s2 starts with j for length k

		for (int i1 = length - 1; i1 >= 0; i1--) {
			for (int i2 = length - 1; i2 >= 0; i2--) {
				for (int k = 1; k <= length - Math.max(i1, i2); k++) { // pitfall length of k from 1 to length - Math.max(i1, i2)
					if (s1.substring(i1, i1 + k).equals(
							s2.substring(i2, i2 + k))) {
						dp[i1][i2][k] = true;
					} else {
						for (int l = 1; l < k; l++) { // cut from 1 to k - 1
							if (dp[i1][i2][l] && dp[i1 + l][i2 + l][k - l]
									|| dp[i1][i2 + k - l][l]
									&& dp[i1 + l][i2][k - l]) {
								dp[i1][i2][k] = true;
								break;
							}
						}
					}
				}
			}
		}

		return dp[0][0][length];
	}

	/*
	 * # 2 DFS
	 */
	public boolean isScrambleDFS(String s1, String s2) {
		if (s1.length() != s2.length())
			return false;

		int[] table = new int[26];
		int length = s1.length();
		for (int i = 0; i < length; i++) {
			table[s1.charAt(i) - 'a']++;
			table[s2.charAt(i) - 'a']--;
		}
		for (int i : table) {
			if (i != 0)
				return false;
		}

		if (length == 1 || s1.equals(s2))
			return true;

		for (int i = 1; i < length; i++) {
			if (isScrambleDFS(s1.substring(0, i), s2.substring(0, i))
					&& isScrambleDFS(s1.substring(i, length),
							s2.substring(i, length))
					|| isScrambleDFS(s1.substring(0, i),
							s2.substring(length - i, length))
					&& isScrambleDFS(s1.substring(i, length),
							s2.substring(0, length - i))) {
				return true;
			}
		}

		return false;
	}
	
    public boolean isScramble1(String s1, String s2) {
        if (!isAnagram(s1, s2)) {
            return false;
        }
        if (s1.length() == 1) {
            return true;
        }
        
        for (int i = 1, len = s1.length(); i < len; i++) {
            if (isScramble(s1.substring(0,i), s2.substring(0, i)) 
                && isScramble(s1.substring(i, len), s2.substring(i, len)) ||
                isScramble(s1.substring(0, i), s2.substring(len - i, len))
                && isScramble(s1.substring(i, len), s2.substring(0, len - i))) {
                    return true;
                }
        }
        
        return false;
    }
    
    private boolean isAnagram(String s1, String s2) {
        if (s1.equals(s2))
            return true;
        if (s1.length() != s2.length())
            return false;
            
        int[] letters = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            letters[s1.charAt(i) - 'a']++;
            letters[s2.charAt(i) - 'a']--;
        }
        for (int i : letters) {
            if (i != 0) return false;
        }
        
        return true;
    }

	/**
	 * 
	 */
	public ScrambleString() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ScrambleString ss = new ScrambleString();
		String s1 = "a";
		String s2 = "a";
		ss.isScramble(s1, s2);
	}

}
